home *** CD-ROM | disk | FTP | other *** search
/ MacHack 2000 / MacHack 2000.toast / pc / The Hacks / Softshoe / Lisa's Mac Parts / Heap / Heap.h < prev    next >
Text File  |  2000-06-23  |  1KB  |  62 lines
  1. // Heap.h
  2.  
  3. #ifndef Heap_h
  4. #define Heap_h
  5.  
  6. #ifndef Integers_h
  7. #include "Integers.h"
  8. #endif
  9. #ifndef Assert_h
  10. #include "Assert.h"
  11. #endif
  12.  
  13. template < class Element > class HeapLink;
  14.  
  15. template < class Element >
  16. class Heap
  17.   {
  18.     typedef Element ElementType;
  19.     typedef HeapLink< Element > LinkType;
  20.     typedef Heap< Element > HeapType;
  21.     typedef bool (ElementType::*Comparator)( const Element& ) const;
  22.     
  23.     private:
  24.         uint32 nodeCount;
  25.         LinkType *top;
  26.         const Comparator below;
  27.         
  28.         LinkType** SubHeap( uint32 path );
  29.         LinkType& RemoveLast();
  30.         
  31.         void SinkNode( LinkType**& subHeap, LinkType*& newNode );
  32.         void Percolate( LinkType** subHeap );
  33.         
  34.         void Validate( LinkType& node, uint32 level ) const;
  35.         
  36.         // Implemented only to allow explicit instantiation
  37.             Heap( const Heap& )                        { Assert( 0 ); }
  38.             void operator=( const Heap& )            { Assert( 0 ); }
  39.         
  40.     public:
  41.         Heap( Comparator below );    // Typically operator<=( const Element& ) const
  42.         ~Heap();
  43.         
  44.         Comparator Below() const    { return below; }
  45.         
  46.         bool IsEmpty() const            { return top == 0; }
  47.         
  48.         LinkType& Top() const        { Assert( top != 0 ); return *top; }
  49.         LinkType& Pop();
  50.         
  51.         void Add( LinkType& );
  52.         void Remove( LinkType& );
  53.         
  54.         void Validate() const;         // Checks a set of assertions
  55.   };
  56.  
  57. #ifndef Heap_cp
  58. #include "Heap.cp"
  59. #endif
  60.  
  61. #endif
  62.